/*
 *   项目名称：leetcode-algo
 *   文件名称：com.xiaolon.prob.bag.Bag
 *
 *   创建人：  ZHOU XIAO LONG
 *   创建日期：2024/9/30
 *
 */
package com.xiaolon.prob.bag;/*
 * 类描述：Bag 背包常见问题
 */
import com.google.common.primitives.Ints;
import org.junit.jupiter.api.Test;
import org.junit.jupiter.params.ParameterizedTest;
import org.junit.jupiter.params.provider.Arguments;
import org.junit.jupiter.params.provider.MethodSource;
import org.junit.jupiter.params.provider.ValueSource;

import java.util.*;
import java.util.stream.Stream;

public class Bag {

    public String destCity(List<List<String>> paths) {
        Map<String,int[]> map = new HashMap<>();

        for(List<String> path : paths){
            String from = path.get(0);
            String to = path.get(1);
            map.getOrDefault(from, new int[]{0,0})[0]++;
            map.getOrDefault(to, new int[]{0,0})[1]++;
        }

        String ans=null;
        for(Map.Entry<String,int[]> entry : map.entrySet()){
            String key = entry.getKey();
            int[] value = entry.getValue();
            if(value[0] >0 && value[1] == 0){
                ans = key;
                break;
            }

        }
        return ans;
    }

    @ParameterizedTest
    @MethodSource(value = "maxGoodNumberProvider")
    public void maxGoodNumberTest(int[] nums){
        System.out.println(maxGoodNumber(nums));
    }
    public static Stream<int[]> maxGoodNumberProvider(){
        return Stream.of(
                new int[]{1,2,3},
                new int[]{2,8,16}
        );
    }

    public int maxGoodNumber(int[] nums) {
        // 暴力解法
        // 截取二进制表示
        int ans = 0;

        for(int i=0;i<3;i++){
            for(int j=0;j<3 && j!=i ;j++){
                if(j!=i){
                    StringBuilder sb = new StringBuilder();
                    sb.append(Integer.toBinaryString(nums[i]));
                    sb.append(Integer.toBinaryString(nums[j]));
                    sb.append(Integer.toBinaryString(nums[3-i-j]));

                    System.out.println("i:"+i +" j:" + j +" "+sb.toString());

                    Integer temp = Integer.valueOf(sb.toString(), 2);
                    ans = temp > ans? temp:ans;
                }

            }
        }
        return ans;
    }


    @ParameterizedTest
    @MethodSource(value = "combinationSum4Provider")
    public void combinationSum4Test(int[] nums, int target){
        System.out.println(combinationSum4(nums, target));
    }

    public static Stream<Arguments> combinationSum4Provider(){
        return Stream.of(
                Arguments.of(new int[]{1,2,3},4),
                Arguments.of(new int[]{9},3)
        );
    }

    public int combinationSum4(int[] nums, int target) {
        int[] dp = new int[target + 1];
        dp[0] = 1;
        for (int i = 1; i <= target; i++) {
            for (int num : nums) {
                if (num <= i) {
                    dp[i] += dp[i - num];
                }
            }
        }
        System.out.println(Arrays.toString(dp));
        return dp[target];
    }



    @ParameterizedTest
    @MethodSource(value = "minCostProvider")
    void minCostTest(int maxTime, int[][] edges, int[] passingFees) {
        System.out.println(minCost(maxTime, edges, passingFees));
    }

    public static Stream<Arguments> minCostProvider(){
        return Stream.of(
                Arguments.of(30, new int[][]{{0,1,10},{1,2,10},{2,5,10},{0,3,1},{3,4,10},{4,5,15}}, new int[]{5,1,2,20,20,3}),
                Arguments.of(29, new int[][]{{0,1,10},{1,2,10},{2,5,10},{0,3,1},{3,4,10},{4,5,15}}, new int[]{5,1,2,20,20,3}),
                Arguments.of(25, new int[][]{{0,1,10},{1,2,10},{2,5,10},{0,3,1},{3,4,10},{4,5,15}}, new int[]{5,1,2,20,20,3})
        );
    }

    /**
     * leetcode 128 规定时间内到达终点最小花费
     * @param maxTime
     * @param edges
     * @param passingFees
     * @return
     */
    public int minCost(int maxTime, int[][] edges, int[] passingFees) {
        /**
         * 使用队列来存储遍历终点：广度遍历方式
         */
        //[起点，终点，时间，费用]
        Map<Integer, List<List<Integer>>> map = new HashMap<>();
        for (int[] edge : edges) {
            int start = edge[0];
            List<List<Integer>> value = map.get(Integer.valueOf(start));
            if(value==null){
                List<List<Integer>> list = new ArrayList<>();
                list.add(Arrays.asList(edge[0], edge[1], edge[2]));
                map.put(Integer.valueOf(start), list);
            }else{
                value.add(Arrays.asList(edge[0], edge[1], edge[2]));
            }
        }


        Deque<int[]> queue = new LinkedList<>();
        List<List<Integer>> available = new ArrayList<>();
        // 找出起点为0的边
        for (int[] edge : edges) {
            if(edge[0] == 0) queue.offer(new int[]{edge[0], edge[1], edge[2], passingFees[0]});
        }

        while(!queue.isEmpty()) {
            int size = queue.size();

            for (int i = 0; i < size; i++) {
                // 寻找下一条
                int[] edge = queue.poll();
                int start = edge[0], end = edge[1], time = edge[2], cost = edge[3];
                // 判断终点是否为n-1
                if(end == passingFees.length-1){
                    available.add(Arrays.asList(start, end, time, cost+passingFees[end]));
                }
                List<List<Integer>> lists = map.get(Integer.valueOf(end));
                if(lists != null) {
                    for (List<Integer> list : lists) {
                        int start1 = list.get(0);
                        int end1 = list.get(1);
                        int time1 = list.get(2);
                        int cost1 = passingFees[start1];

                        queue.offer(new int[]{start, end1, time+time1, cost+cost1});
                    }
                }
            }
        }

        if(available.size() == 0) return -1;

        int minFree=Integer.MAX_VALUE;
        int minTime = Integer.MAX_VALUE;
        for (List<Integer> list : available) {
            minTime = list.get(2)<minTime?list.get(2):minTime;

            if(list.get(2) <= maxTime) minFree = list.get(3)<minFree?list.get(3):minFree;
        }
        if(minTime > maxTime) return -1;
        return minFree==Integer.MAX_VALUE?0:minFree;
    }


    /**
     * leetcode 279 完全平方数
     * @param n
     * @return
     */
    public int numSquares(int n) {
        // 动态规划
        int[] f = new int[n+1];
        for (int i = 1; i <= n; i++) {
            // 更新操作
            int min = Integer.MAX_VALUE;
            for(int j = 1; j*j <=i; j++){
                min = Math.min(min, f[i - j*j]);  // 分解子问题
            }
            f[i] = min+1;
        }
        return f[n];
    }

    @ParameterizedTest
    @ValueSource(ints = {12, 13})
    public void numSquaresTest(int n){
        Bag bag = new Bag();
        System.out.println(bag.numSquares(n));
    }

}
